1. Field of the Invention
The present invention is directed to a device and method for providing fast, secure encryption. The fast, secure encryption is provided by an improved cryptographically secure pseudo-random bit generator that quickly provides long, secure, random bit strings.
2. Description of Related Art
The generation of random numbers (or seemingly random numbers, as discussed below) is used in many processes. Processes which use random numbers as auxiliary inputs include sorting, simulation and testing of complex systems, encryption, and other cryptographic processes. Often, high-speed cryptographic applications require a long string of random numbers which cannot be produced quickly enough directly from physical devices.
The "randomness" of the auxiliary input may be quite important to the process. For example, the "randomness" of a random number generator is often important to the security of a cryptosystem. A poor random number generator may cause correlation and reproducibility problems which could allow an adversary to attack a cryptosystem. On the other hand, a perfectly random number generator may not be possible. It is believed that it is impossible to produce a truly random sequence on a computer. This is because data is input into a computer, the computer performs on the data a predictable process for which it has been programmed, and the computer generates a predictable (to someone knowing the process) output.
As a result, pseudo-random sequence generators were developed. A pseudo-random sequence generator provides a very large number of random bits. A pseudo-random generator is sometimes defined as a generator which "looks" random. That is, it passes well-known statistical tests of randomness. A general purpose pseudo-random generator is not suitable for many applications, such as certain cryptography applications. It is important that the generator used for cryptographic applications, for example, is cryptographically secure. This means:
Let the generator be G(s)=R, s .epsilon.{0, 1}.sup.n, R .epsilon.{0, 1}.sup.m, m&gt;n; where:
R is a generated random bit string; PA1 s is the seed for the bit string; PA1 n is an integer; and PA1 m is the number of bits in the bit string. PA1 R=b.sub.1, b.sub.2, . . . , b.sub.i+1, . . . , b.sub.m.
A bit test is then performed in the following manner:
Keeping s secret, one reveals all of R except one bit:
Then, for all bits b.sub.i, any algorithm having a feasible run time should not be able to guess the unrevealed bit with a probability greater than 1/2. Of course, one can perform an exhaustive search for the seed s and compute the bit exactly, but that would take an infeasible amount of time. The requirement of being cryptographically strong asks that this exhaustive search is just about the best way to do this attack. That is, in addition to "looking random", as with a general purpose pseudo-random generator discussed above, a "cryptographically secure pseudo-random (CSPR) bit generator" is sometimes defined as being unpredictable. That is, it is computationally infeasible to predict what the next random number will be, even given complete knowledge of the algorithm or hardware generating the sequence and all of the previous bits in the bit string.
In conventional implementations, a CSPR bit generator is a generator which takes a short, random seed as an input, then sequentially repeates a one-way function (such as DES or a one-way hash function) using part of the function output or the entire function output as input for the next iteration. This repeated use of a one-way function produces a long pseudo-random bit string which is indistinguishable from a truly random bit string. (Briefly, a one-way function is a function that is easy to compute but hard to invert on an overwhelming fraction of its range.)
One problem associated with conventional CSPR bit generators described above is experienced in software encryption. Software encryption presents a bottleneck in many real-time applications such as video-stream encryption and TCP/IP layer encryption. A typical attempt to use ciphers like DES for encrypting video on-line software on a work station, for example, results in the video freezing up after a few seconds. This is due to the fact that the additional overhead typically needed to perform the encryption is significant. It is desirable to have an algorithm that adds only such a small overhead that the performance does not change noticeably when encryption is added. Similar comments apply to encryption of packets at the kernel level for Internet applications.
One solution to this problem is to design new encryption algorithms. This solution is impractical. That is because before a new cryptosystem is trusted to be secure, the new algorithm should be studied and attacks to "crack" the cryptosystem should be performed on it. Alternately, one can develop fast algorithms that can be used on any (trusted) existing cipher (as a substitute) in such a way that it is possible to argue that attacking it would imply attacking a trusted cipher or another trusted cryptographic process. An example of a trusted cipher, of course, is DES. It is preferable to avoid dependence on any one particular cipher, however, so that any cipher may be used. As a result, the new algorithm would be just as secure as the one actually used. In this case, one should have the formal argument and its practical implications tested. But the user can avoid more exhausting and expensive cryptanalysis of a new construction.
A second, more practical solution is found in U.S. Pat. No. 5,515,307 ("the '307 patent"), described above. The preferred embodiment of the invention described in the '307 patent uses a slow pseudo-random number generator as a pre-processing step to generating a long random bit string. The device described in the '307 patent works by first producing secure random bits using a slow but strong generator. Then, it "stretches" this string using some specialized constructions based on Random Affine Codes and expander graphs. The '307 patent describes a device which may use any cipher. This device is a random number generator which provides long strings and has provable security properties.
It is an object of the present invention to provide a CSPR bit generator which reduces the bottle neck during software encryption.
It is another object of the present invention to reduce the overhead during encryption.
It is yet another object of the present invention to provide fast, secure encryption using an improved CSPR bit generator.
It is a further object of the present invention to provide a CSPR bit generator using less memory than previous CSPR bit generators.